/**
 * @param {number} n
 * @param {number[][]} flights
 * @param {number} src
 * @param {number} dst
 * @param {number} k
 * @return {number}
 */
export var findCheapestPrice = function (n, flights, src, dst, k) {
  // dp[i][j]为经过i条边从src点到达j点的最小花费,有k个途经点就有k+1条边，
  // dp以从0条边到第k+1条边算
  const dp = new Array(k + 2).fill(0).map(() => new Array(n).fill(Infinity))
  // init: src经过0过站到达src点，花费为0
  dp[0][src] = 0
  let ans = Infinity
  // 开始计算dp的值
  for (let i = 1; i <= k + 1; i++) {
    for (const fl of flights) {
      const [from, to, cost] = fl
      // 取出去到from点的最小花费，加上从from点到to点的花费
      dp[i][to] = Math.min(dp[i][to], dp[i - 1][from] + cost)
    }
    ans = Math.min(ans, dp[i][dst])
  }
  return ans === Infinity ? -1 : ans
}
